"""linked_list.py
链表（Linked List）是一种基础数据结构，它是由一系列节点组成的，每个节点包含一个数据元素和一个指向下一个节点的指针。这种结构允许在插入和删除元素时不需要移动和重构整个数据结构。常见的链表操作包括添加（add），删除（remove），查找（get/find），设置（set），求链表长度（size）等。

接下来我们将使用 Python 来实现一个简单的单链表。
链表的类将包含以下操作：
添加元素(add)
删除元素(remove)
查找元素(get)
链表是否为空(is_empty)
链表的长度(size)。

"""

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self):
        self.head = None

    def is_empty(self):
        return self.head is None

    def add(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node # node 是容器，赋值是传引用容器的地址

    def size(self):
        node = self.head
        count = 0
        while node:
            count += 1
            node = node.next
        return count

    def get(self, index):
        node = self.head
        for i in range(index):
            if not node:
                return None
            node = node.next
        return node.data if node else None

    def remove(self, data):
        node = self.head
        prev_node = None
        while node:
            if node.data == data:
                if prev_node:
                    prev_node.next = node.next
                else:
                    self.head = node.next
                return True
            prev_node = node
            node = node.next
        return False
    
    def print(self):
        node = self.head
        print('-head->', end='')
        while node:
            print(node.data, end='->')
            node = node.next
        print('None')


if __name__ == '__main__':
    ll = LinkedList()
    print(ll.is_empty())  # True

    ll.add(1)
    ll.add(2)
    ll.add(3)
    print(ll.size())  # 3
    ll.print() #-head->3->2->1->None
    print(ll.get(1))  # 2

    ll.remove(2)
    print(ll.get(1))  # 1

    print(ll.size())  # 2
    ll.print() # -head->3->1->None